Location-based services are becoming increasingly popular. However, using a public cloud for offering location-based services exposes valuable information. The cloud provider that offers the service is able to track objects, users, and queries made to the service. A company using the service exposes e.g. the location, movements, and areas of interest of assets and employees, which can be undesirable. In fact, many companies are hesitant about using such cloud services because they fear leakage of their critical location data, potentially to unauthorized/untrusted parties. Hence, concealing location information from untrusted parties is critical for wider-spread adoption of cloud-based location services.
An example for a location-based service is geo-fencing, where events are triggered when people or devices enter or leave a defined area. To conceal the location information while still using public-cloud-based location services requires a transformation of the location information in a way that the output can still be processed by the location-based service. State-of-the-Art includes order preserving encryption (OPE), which however can only provide a weak level of concealment, See R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu “Order-Preserving Encryption for Numeric Data” in SIGMOD, 2004, because it preserves the relative location between points. Another option is adding noise to the data, which again offers only weak concealment but also reduces the quality of the service. Current approaches can only provide k-anonymity by clustering all nearby nodes in order to hide their actual identity, basically by adding noise to the spacial location and time of request, See B. Gedik and L. Liu “Location Privacy in Mobile Systems: A Personalized Anonymization Model” in ICDCS, 2005, M. Gruteser and D. Grunwald “Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking” in USENIX MobiSys, 2003, P. Kalnis, G. Ghinita, K. Mouratidis, and D. Papadias “Preventing Location-Based Identity Inference in Anonymous Spatial Queries”, IEEE TKDE, 19(12):1719-1733, 2007, and M. F. Mokbel, C.-Y. Chow, and W. G. Aref “The New Casper: Query Processing for Location Services without Compromising Privacy” in VLDB, 2006.